{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Prime Arrangements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numPrimeArrangements"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #质数排列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>请你帮忙给从 <code>1</code> 到 <code>n</code>&nbsp;的数设计排列方案，使得所有的「质数」都应该被放在「质数索引」（索引从 1 开始）上；你需要返回可能的方案总数。</p>\n",
    "\n",
    "<p>让我们一起来回顾一下「质数」：质数一定是大于 1 的，并且不能用两个小于它的正整数的乘积来表示。</p>\n",
    "\n",
    "<p>由于答案可能会很大，所以请你返回答案 <strong>模 mod&nbsp;<code>10^9 + 7</code></strong>&nbsp;之后的结果即可。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 5\n",
    "<strong>输出：</strong>12\n",
    "<strong>解释：</strong>举个例子，[1,2,5,4,3] 是一个有效的排列，但 [5,2,3,4,1] 不是，因为在第二种情况里质数 5 被错误地放在索引为 1 的位置上。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 100\n",
    "<strong>输出：</strong>682289015\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 100</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [prime-arrangements](https://leetcode.cn/problems/prime-arrangements/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [prime-arrangements](https://leetcode.cn/problems/prime-arrangements/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5', '100']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        l , k , ans = 0 , 1 , 1\n",
    "        nums = [2 , 3 , 5 , 7 , 11 , 13 , 17 , 19 , 23 , 29 , 31 , 37 , 41 , 43 , 47 , 53 , 59 , 61 , 67 , 71 , 73 , 79 , 83 , 89 , 97]\n",
    "        for i in range(1,n+1):\n",
    "            if i in nums:\n",
    "                l += 1\n",
    "            else:\n",
    "                ans *= k\n",
    "                k += 1\n",
    "                \n",
    "        for j in range(1,l+1):\n",
    "            ans *= j\n",
    "            if ans > 10**9+7 :\n",
    "                ans = ans % (10**9+7)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        def isPrimeNumber(n) -> bool:\n",
    "            for ele in range(2, int(n**(1/2))+1):\n",
    "                if not n % ele:\n",
    "                    return False\n",
    "            # 质数返回True\n",
    "            return True\n",
    "        prime_cnt = 0\n",
    "        for ele in range(2, n+1):\n",
    "            prime_cnt += 1 if isPrimeNumber(ele) else 0\n",
    "        return math.factorial(prime_cnt) * math.factorial(n-prime_cnt) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        count = 0\n",
    "        for i in range(2,n+1):\n",
    "            flag = 0\n",
    "            for j in range(2,i):\n",
    "                if i%j==0:\n",
    "                    flag=1\n",
    "                    break\n",
    "            if flag==0:\n",
    "                count += 1\n",
    "        res = 1\n",
    "        for i in range(1,count+1):\n",
    "            res = (res*i)%1000000007\n",
    "        for i in range(1,n-count+1):\n",
    "            res = (res*i)%1000000007\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        m=10**9+7\n",
    "        x=[1]\n",
    "        for i in range(2,n+1):\n",
    "            for j in [2,3,5,7]:\n",
    "                if i%j==0 and i//j!=1:\n",
    "                    x.append(i)\n",
    "                    break\n",
    "        a=len(x) #75\n",
    "        b=n-a #25\n",
    "        s1=1\n",
    "        s2=1\n",
    "        for i in range(1,a+1):\n",
    "            s1*=i\n",
    "        for j in range(1,b+1):\n",
    "            s2*=j\n",
    "        return (s1*s2)%m"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        numPrimes = sum(self.isPrime(i) for i in range(1, n + 1))\n",
    "        return self.factorial(numPrimes) * self.factorial(n - numPrimes) % (10 ** 9 + 7)\n",
    "\n",
    "    def isPrime(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        for i in range(2, int(sqrt(n)) + 1):\n",
    "            if n % i == 0:\n",
    "                return 0\n",
    "        return 1\n",
    "\n",
    "    def factorial(self, n: int) -> int:\n",
    "        res = 1\n",
    "        for i in range(1, n + 1):\n",
    "            res *= i\n",
    "            res %= (10 ** 9 + 7)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isprime(self, n: int):\n",
    "        i = 2\n",
    "        while i*i <= n:\n",
    "            if n % i == 0: # \n",
    "                return False\n",
    "            i+=1\n",
    "        return True \n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        primeNums = 1 # 2\n",
    "        nums = 1  #1\n",
    "        A = 1\n",
    "        B = 1\n",
    "        for k in range(3,n+1):\n",
    "            if self.isprime(k):\n",
    "                primeNums += 1 # 2\n",
    "                A *= primeNums%((10**9)+7)\n",
    "            else:\n",
    "                nums+=1\n",
    "                B *= nums%((10**9)+7)\n",
    "            \n",
    "        return (A*B)%((10**9)+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        def isPrime(n):\n",
    "            for i in range(2, isqrt(n) + 1):\n",
    "                if n % i == 0:\n",
    "                    return 0\n",
    "            return 1\n",
    "\n",
    "        cnt = sum(map(isPrime, range(2, n+1)))\n",
    "        return perm(cnt, cnt) * perm(n - cnt, n - cnt) % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        dict_ = {1: None}\n",
    "        for i in range(2, int(math.sqrt(n))+1):\n",
    "            if i not in dict_:\n",
    "                j = 2\n",
    "                while True:\n",
    "                    if i*j>n:\n",
    "                        break\n",
    "                    dict_[i*j] = None\n",
    "                    j += 1\n",
    "        h = 0\n",
    "        for i in dict_:\n",
    "            h += 1\n",
    "        return self.factorial(h)*self.factorial(n-h)%(10**9+7)\n",
    "    def factorial(self, n) -> int:\n",
    "        if n <= 1:\n",
    "            return 1\n",
    "        return self.factorial(n-1)*n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        length = 0\n",
    "        def isprime(num):\n",
    "            if n==1:\n",
    "                return False\n",
    "            for i in range(2,int(math.sqrt(num))+1):\n",
    "                if num%i == 0:\n",
    "                    return False\n",
    "            return True\n",
    "        for i in range(1,n+1,2):\n",
    "            if isprime(i):\n",
    "                length += 1\n",
    "        \n",
    "        return ((math.factorial(length)%(10**9+7))*(math.factorial(n-length)%(10**9+7)))%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        return [\"happy_cat\", 1, 1, 2, 4, 12, 36, 144, 576, 2880, 17280, 86400, 604800, 3628800, 29030400, 261273600, 612735986, 289151874, 180670593, 445364737, 344376809, 476898489, 676578804, 89209194, 338137903, 410206413, 973508979, 523161503, 940068494, 400684877, 13697484, 150672324, 164118783, 610613205, 44103617, 58486801, 462170018, 546040181, 197044608, 320204381, 965722612, 554393872, 77422176, 83910457, 517313696, 36724464, 175182841, 627742601, 715505693, 327193394, 451768713, 263673556, 755921509, 94744060, 600274259, 410695940, 427837488, 541336889, 736149184, 514536044, 125049738, 250895270, 39391803, 772631128, 541031643, 428487046, 567378068, 780183222, 228977612, 448880523, 892906519, 858130261, 622773264, 78238453, 146637981, 918450925, 514800525, 828829204, 243264299, 351814543, 405243354, 909357725, 561463122, 913651722, 732754657, 430788419, 139670208, 938893256, 28061213, 673469112, 448961084, 80392418, 466684389, 201222617, 85583092, 76399490, 500763245, 519081041, 892915734, 75763854, 682289015][n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        def factorial(n):\n",
    "            if n <= 1:\n",
    "                return 1\n",
    "            return n * factorial(n - 1)\n",
    "        \n",
    "        primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101]\n",
    "\n",
    "        primeCount = 0\n",
    "        while primes[primeCount] <= n:\n",
    "            primeCount += 1\n",
    "        return factorial(primeCount) * factorial(n-primeCount) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        res = 1\n",
    "        a,b = 0,1\n",
    "        for i in range(2,n + 1):\n",
    "            p = True\n",
    "            for j in range(2,int(i ** 0.5) + 1):\n",
    "                if i % j == 0:\n",
    "                    p = False\n",
    "                    break\n",
    "            if p:\n",
    "                a += 1\n",
    "                res *= a\n",
    "            else:\n",
    "                b += 1\n",
    "                res *= b\n",
    "        return res % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        def is_prime( n: int) -> int:\n",
    "            if n == 1:\n",
    "                return 0\n",
    "            for i in range(2, int(sqrt(n)) + 1):\n",
    "                if n % i == 0:\n",
    "                    return 0\n",
    "            return 1\n",
    "\n",
    "        def factorial( n: int) -> int:\n",
    "            res = 1\n",
    "            for i in range(1, n + 1):\n",
    "                res *= i\n",
    "                res %= (10 ** 9 + 7)\n",
    "            return res\n",
    "        numPrimes = sum(is_prime(i) for i in range(1, n + 1))\n",
    "        return factorial(numPrimes) * factorial(n - numPrimes) % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        numPrimes = sum(self.isPrime(i) for i in range(1,n+1))\n",
    "        return self.factorial(numPrimes) * self.factorial( n-numPrimes)%(10**9+7)\n",
    "    \n",
    "    def isPrime(self,n):\n",
    "        if n==1:\n",
    "            return 0\n",
    "        for i in range(2,int(sqrt(n)+1)):\n",
    "            if n%i==0:\n",
    "                return 0\n",
    "        return 1 #是质数返回1\n",
    "    \n",
    "    def factorial(self,n):\n",
    "        res=1\n",
    "        for i in range(1,n+1):\n",
    "            res*=i\n",
    "            res%=(10**9+7)\n",
    "        return res  #阶乘取模(10**9+7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        numPrime=sum(self.isPrime(i) for i in range(1,n+1))\n",
    "        return self.factorial(numPrime)*self.factorial(n-numPrime)%(10**9+7)\n",
    "\n",
    "    def isPrime(self,n:int)->int:\n",
    "        if n==1:\n",
    "            return 0\n",
    "        for i in range(2,int(sqrt(n))+1):\n",
    "            if n%i==0:\n",
    "                return 0\n",
    "        return 1\n",
    "\n",
    "    def factorial(self,n:int)->int:\n",
    "        res=1\n",
    "        for i in range(1,n+1):\n",
    "            res*=i\n",
    "            res %=(10**9+7)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        def isPrime(i):\n",
    "            if i==1:\n",
    "                return False\n",
    "            for j in range(2, int(sqrt(i))+1):\n",
    "                if i%j == 0:\n",
    "                    return False\n",
    "            return True\n",
    "        cnt = sum(isPrime(i+1) for i in range(n))\n",
    "        return perm(cnt) * perm(n-cnt) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        def eratosthenes(a):\n",
    "            lst = [True] * (a + 1)\n",
    "            lst[0] = False\n",
    "            lst[1] = False\n",
    "            for i in range(2, int(a ** 0.5) + 1):\n",
    "                if lst[i]:\n",
    "                    for j in range(i * i, a + 1, i):\n",
    "                        lst[j] = False\n",
    "            return lst.count(True)\n",
    "\n",
    "        def factorial(a):\n",
    "            if a == 1 or a == 0:\n",
    "                return 1\n",
    "            return a * factorial(a - 1)\n",
    "\n",
    "        mod = int(1e9 + 7)\n",
    "        p = eratosthenes(n)\n",
    "        q = n - p\n",
    "        return factorial(p) * factorial(q) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        def fac(t):\n",
    "            s=1\n",
    "            for i in range(2,t+1):\n",
    "                s=s*i\n",
    "            return s\n",
    "        count=0\n",
    "        for i in range(2,n+1):\n",
    "            for j in range(2,i):\n",
    "                if i%j==0:\n",
    "                    break\n",
    "            else:\n",
    "                count+=1\n",
    "        return (fac(count)*fac(n-count))%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        cnt = 0\n",
    "        for j in range(2, n+1):\n",
    "            for i in range(2, isqrt(j) + 1):\n",
    "                if j % i == 0:\n",
    "                    break\n",
    "            else:\n",
    "                cnt += 1\n",
    "\n",
    "        return factorial(cnt) * factorial(n - cnt) % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        if n <= 2:\n",
    "            return 1\n",
    "        p = 1\n",
    "        for i in range(3, n+1):\n",
    "            t = 2\n",
    "            while t**2 <= i:\n",
    "                if i%t == 0:\n",
    "                    break\n",
    "                t += 1\n",
    "            else:\n",
    "                p += 1\n",
    "        ans = 1\n",
    "        for i in range(1, p+1):\n",
    "            ans *= i\n",
    "            ans %= (10**9+7)\n",
    "        for i in range(1, n-p+1):\n",
    "            ans *= i\n",
    "            ans %= (10**9+7)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        numPrimes = sum(self.isPrime(i) for i in range(1, n + 1))\n",
    "        return self.factorial(numPrimes) * self.factorial(n - numPrimes) % (10 ** 9 + 7)\n",
    "\n",
    "    def isPrime(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        for i in range(2, int(sqrt(n)) + 1):\n",
    "            if n % i == 0:\n",
    "                return 0\n",
    "        return 1\n",
    "\n",
    "    def factorial(self, n: int) -> int:\n",
    "        res = 1\n",
    "        for i in range(1, n + 1):\n",
    "            res *= i\n",
    "            res %= (10 ** 9 + 7)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        def isprime(k):\n",
    "            if k ==1:\n",
    "                return 0\n",
    "            \n",
    "            for i in range(2,int(sqrt(k)+1)):\n",
    "                if k %i ==0:\n",
    "                    return 0\n",
    "            return 1\n",
    "        cnt =0\n",
    "        for i in range(1,n+1):\n",
    "            cnt += isprime(i)\n",
    "        ans =1\n",
    "        for i in range(1,n-cnt+1):\n",
    "            ans *= i\n",
    "            ans %= MOD\n",
    "        res =1\n",
    "        for i in range(1,cnt+1):\n",
    "            res *=i\n",
    "            res %= MOD\n",
    "        return (ans*res)%MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isprime(self, n: int):\n",
    "        i = 2\n",
    "        while i*i <= n:\n",
    "            if n % i == 0: # \n",
    "                return False\n",
    "            i+=1\n",
    "        return True \n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        primeNums = 1 # 2\n",
    "        nums = 1  #1\n",
    "        A = 1\n",
    "        B = 1\n",
    "        for k in range(3,n+1):\n",
    "            if self.isprime(k):\n",
    "                primeNums += 1 # 2\n",
    "                A *= primeNums\n",
    "            else:\n",
    "                nums+=1\n",
    "                B *= nums\n",
    "            if A*B>((10**9)+7):\n",
    "                A= A%((10**9)+7)\n",
    "                B= B%((10**9)+7)\n",
    "        return (A*B)%((10**9)+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPrime(self, x):\n",
    "        if x <= 1:\n",
    "            return False\n",
    "        \n",
    "        s = 2\n",
    "        e = int(x**(1/2))\n",
    "        while True:\n",
    "            if s > e:\n",
    "                break\n",
    "            else:\n",
    "                if x % s == 0:\n",
    "                    return False\n",
    "            s += 1\n",
    "        return True\n",
    "\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        j = 1\n",
    "        k = 1\n",
    "        result = 1\n",
    "        for i in range(1, n+1):\n",
    "            if self.isPrime(i):\n",
    "                result *= j\n",
    "                j += 1\n",
    "            else:\n",
    "                result *= k\n",
    "                k += 1\n",
    "\n",
    "        return result % (10**9 + 7)\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPrime(self, x):\n",
    "        if x <= 1:\n",
    "            return False\n",
    "        \n",
    "        s = 2\n",
    "        e = int(x**(1/2))\n",
    "        while True:\n",
    "            if s > e:\n",
    "                break\n",
    "            else:\n",
    "                if x % s == 0:\n",
    "                    return False\n",
    "            s += 1\n",
    "        return True\n",
    "\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        j = 1\n",
    "        k = 1\n",
    "        result = 1\n",
    "        for i in range(1, n+1):\n",
    "            if self.isPrime(i):\n",
    "                result *= j\n",
    "                j += 1\n",
    "            else:\n",
    "                result *= k\n",
    "                k += 1\n",
    "\n",
    "        return result % (10**9 + 7)\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        li = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29,\n",
    "              31, 37, 41, 43, 47, 53, 59, 61, 67, 71,\n",
    "              73, 79, 83, 89, 97]\n",
    "        is_p = 0\n",
    "        def factorial_iterative(n):\n",
    "            result = 1\n",
    "            for i in range(1, n + 1):\n",
    "                result *= i\n",
    "            return result\n",
    "        for i in range(1, n+1):\n",
    "            if i in li:\n",
    "                is_p += 1\n",
    "        \n",
    "        return int((factorial_iterative(is_p) * factorial_iterative(n-is_p)) % (1000000000 + 7))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        def myfunc(num:int)->bool:\n",
    "            if num == 2 :\n",
    "                return True\n",
    "            for i in range(2,math.ceil(math.sqrt(num))+1):\n",
    "                if num % i == 0:\n",
    "                    return False\n",
    "            return True\n",
    "        def myfunc2(num:int)->int:\n",
    "            ans = 1\n",
    "            for i in range(1,num+1):\n",
    "                ans = (ans * i) % mod\n",
    "            return ans\n",
    "        p,q = 0,1\n",
    "        for i in range(2,n+1):\n",
    "            if myfunc(i) :\n",
    "                p += 1\n",
    "            else :\n",
    "                q += 1\n",
    "        p,q = myfunc2(p),myfunc2(q)\n",
    "        return p*q%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        import sys\n",
    "        sys.setrecursionlimit(30000)\n",
    "        def zhi(x):\n",
    "            if x==1:\n",
    "                return 0\n",
    "            elif x==2:\n",
    "                return 1\n",
    "            else:\n",
    "                for i in range(2,int(x**0.5+1)):\n",
    "                    if x%i==0:\n",
    "                        return 0\n",
    "            return 1\n",
    "        zhinum = 0\n",
    "        he = 0\n",
    "        for i in range(1,n+1):\n",
    "            if zhi(i):\n",
    "                zhinum = zhinum+1\n",
    "            else:\n",
    "                he = he+1\n",
    "        def jie(x):\n",
    "            res = 1\n",
    "            for i in range(1,x+1):\n",
    "                res = res*i\n",
    "            return res\n",
    "        return jie(zhinum)*jie(he)%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPrime(self, x):\n",
    "        if x <= 1:\n",
    "            return False\n",
    "        \n",
    "        s = 2\n",
    "        e = int(x**(1/2))\n",
    "        while True:\n",
    "            if s > e:\n",
    "                break\n",
    "            else:\n",
    "                if x % s == 0:\n",
    "                    return False\n",
    "            s += 1\n",
    "        return True\n",
    "\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        j = 1\n",
    "        k = 1\n",
    "        result = 1\n",
    "        for i in range(1, n+1):\n",
    "            if self.isPrime(i):\n",
    "                result *= j\n",
    "                j += 1\n",
    "            else:\n",
    "                result *= k\n",
    "                k += 1\n",
    "\n",
    "        return result % (10**9 + 7)\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        if n ==1 or n == 2:\n",
    "            return 1\n",
    "        arr = [1 for i in range(0, n+1)]\n",
    "        arr[1] = 0\n",
    "        arr[0] = 0\n",
    "        for i in range(2, n):\n",
    "            for j in range(2, n):\n",
    "                if i * j > n:\n",
    "                    break\n",
    "                arr[i*j] = 0\n",
    "\n",
    "        print(arr)\n",
    "        nums_prime = sum(arr[1:])\n",
    "        nums_not_prime = n - nums_prime\n",
    "        a = math.factorial(nums_prime)\n",
    "        b = math.factorial(nums_not_prime)\n",
    "        return int(a * b % (10**9 + 7))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def isPrime(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        for i in range(2, int(sqrt(n)) + 1):\n",
    "            if n % i == 0:\n",
    "                return 0\n",
    "        return 1\n",
    "    \n",
    "    def factorial(self, n: int) -> int:\n",
    "        res = 1\n",
    "        for i in range(1, n + 1):\n",
    "            res *= i\n",
    "            res %= (10 ** 9 + 7)\n",
    "        return res\n",
    " \n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "\n",
    "        numPrimes = sum(self.isPrime(i) for i in range(1, n + 1))\n",
    "        return self.factorial(numPrimes) * self.factorial(n - numPrimes) % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        def isprime(num):\n",
    "            #print(int(num**0.5)+1)\n",
    "            if num==2:return True\n",
    "            if num%2==0:return False\n",
    "            for t in range(3,int(num**0.5)+1,2):\n",
    "                if num%t==0:return False \n",
    "            return True\n",
    "\n",
    "        p,not_p = 0,1  # not_p代表非质数的数量，1不是质数，所以初值应为1\n",
    "        res=1\n",
    "        for i in range(2,n+1):\n",
    "            if isprime(i):\n",
    "                p+=1\n",
    "            else:not_p+=1\n",
    "        for i in range(1,p+1):\n",
    "            res=res*i\n",
    "        for i in range(1,not_p+1):\n",
    "            res=res*i\n",
    "        tmp = int(1e9+7)\n",
    "        #print(p,not_p,res,tmp)\n",
    "        return res%tmp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\r\n",
    "class Solution:\r\n",
    "    def numPrimeArrangements(self, n: int) -> int:\r\n",
    "        \r\n",
    "        \r\n",
    "        if n <= 2:\r\n",
    "            return 1\r\n",
    "        count = 0\r\n",
    "        for i in range(2, n + 1):\r\n",
    "            for j in range(2, i // 2 + 1):\r\n",
    "                if i % j == 0:\r\n",
    "                    break\r\n",
    "            else:\r\n",
    "                count += 1\r\n",
    "        return math.factorial(count) * math.factorial(n - count) % (10 ** 9 + 7)\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        m=len([x for x in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] if x<=n])\n",
    "        return math.factorial(m)*math.factorial(n-m)%(10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        def isPrime(n):\n",
    "            for i in range(2, isqrt(n) + 1):\n",
    "                if n % i == 0:\n",
    "                    return 0\n",
    "            return 1\n",
    "        cnt = sum(isPrime(i) for i in range(2, n+1))\n",
    "\n",
    "        return perm(cnt, cnt) * perm(n - cnt, n - cnt) % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        def eratosthenes(a):\n",
    "            lst = [True] * (a + 1)\n",
    "            lst[0] = False\n",
    "            lst[1] = False\n",
    "            for i in range(2, int(a ** 0.5) + 1):\n",
    "                if lst[i]:\n",
    "                    for j in range(i * i, a + 1, i):\n",
    "                        lst[j] = False\n",
    "            return lst.count(True)\n",
    "\n",
    "        def factorial(a):\n",
    "            if a == 1 or a == 0:\n",
    "                return 1\n",
    "            return a * factorial(a - 1)\n",
    "\n",
    "        mod = int(1e9 + 7)\n",
    "        p = eratosthenes(n)\n",
    "        q = n - p\n",
    "        ans = factorial(p) * factorial(q) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        numPrimes = sum(self.isPrime(i) for i in range(1, n + 1))\n",
    "        return self.factorial(numPrimes) * self.factorial(n - numPrimes) % (10 ** 9 + 7)\n",
    "    \n",
    "    def isPrime(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        for i in range(2, int(sqrt(n)) + 1):\n",
    "            if n % i == 0:\n",
    "                return 0\n",
    "        return 1\n",
    "    \n",
    "    def factorial(self, n):\n",
    "        res = 1\n",
    "        for i in range(1, n + 1):\n",
    "            res *= i \n",
    "            res %= (10 ** 9 + 7)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "\n",
    "        def factorial(n)->int:\n",
    "            if (n <= 1):\n",
    "                return 1\n",
    "            return n * factorial(n - 1)\n",
    "        \n",
    "        primers = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,\n",
    "                47,53,59,61,67,71,73,79,83,89,97,101]\n",
    "        \n",
    "\n",
    "        primeCount = 0\n",
    "        while (primers[primeCount] <= n):\n",
    "            primeCount += 1\n",
    "        return factorial(primeCount) * factorial(n - primeCount) % (10 **9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        lis = []\n",
    "        if n <=2:\n",
    "            return 1\n",
    "        else:\n",
    "            for i in range(2,n+1):\n",
    "                j = 2\n",
    "                while j < int(i**0.5+1):\n",
    "                    if i%j == 0:\n",
    "                        break\n",
    "                    j+=1\n",
    "                else:\n",
    "                    lis.append(i)\n",
    "            m = len(lis)\n",
    "            print(lis)\n",
    "            res = 1\n",
    "            for i in range(1,m+1):\n",
    "                res *= i\n",
    "            x = n - m\n",
    "            res1 = 1\n",
    "            for j in range(1,x+1):\n",
    "                res1 *= j\n",
    "            rest = (res * res1) % mod\n",
    "            return rest"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        cnt = 0\n",
    "        for j in range(2, n+1):\n",
    "            for i in range(2, isqrt(j) + 1):\n",
    "                if j % i == 0:\n",
    "                    break\n",
    "            else:\n",
    "                cnt += 1\n",
    "\n",
    "        return perm(cnt, cnt) * perm(n - cnt, n - cnt) % (10 ** 9 + 7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        s = set([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,\n",
    "                 61, 67, 71, 73, 79, 83, 89, 97])\n",
    "        num1 = 0\n",
    "        for i in range(1,n+1):\n",
    "            if i in s:\n",
    "                num1 += 1\n",
    "        num2 = n-num1\n",
    "        return (factorial(num1)*factorial(num2)) % (1000000007)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        x = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97]\n",
    "        count = bisect.bisect_right(x, n)\n",
    "        less = n - count     \n",
    "        return (math.factorial(less) * math.factorial(count)) % (10**9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        numPrimes = sum(self.isPrime(i) for i in range(1, n + 1))\n",
    "        return self.factorial(numPrimes) * self.factorial(n - numPrimes) % (10 ** 9 + 7)\n",
    "\n",
    "    def isPrime(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        for i in range(2, int(sqrt(n)) + 1):\n",
    "            if n % i == 0:\n",
    "                return 0\n",
    "        return 1\n",
    "\n",
    "    def factorial(self, n: int) -> int:\n",
    "        res = 1\n",
    "        for i in range(1, n + 1):\n",
    "            res *= i\n",
    "            res %= (10 ** 9 + 7)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        a=0\n",
    "        b=1\n",
    "        c=1\n",
    "        for i in range(2,n+1,1):\n",
    "            for j in range(2,i,1):\n",
    "                if i%j==0:\n",
    "                    break\n",
    "                elif i%j!=0 and j==i-1:\n",
    "                    a=a+1\n",
    "        for j in range(1,a+2,1):\n",
    "            b=b*j\n",
    "        for j in range(1,n-a,1):\n",
    "            c=c*j\n",
    "        return mod(b*c,10**9+7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        numPrimes = sum(self.isPrime(i) for i in range(1, n + 1))\n",
    "        return self.factorial(numPrimes) * self.factorial(n - numPrimes) % (10 ** 9 + 7)\n",
    "\n",
    "    def isPrime(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        for i in range(2, int(sqrt(n)) + 1):\n",
    "            if n % i == 0:\n",
    "                return 0\n",
    "        return 1\n",
    "\n",
    "    def factorial(self, n: int) -> int:\n",
    "        res = 1\n",
    "        for i in range(1, n + 1):\n",
    "            res *= i\n",
    "            res %= (10 ** 9 + 7)\n",
    "        return res\n",
    "        '''\n",
    "        def isprime(number):\n",
    "            if number == 1:\n",
    "                return False\n",
    "            for i in range(2, math.ceil(n**0.5)):\n",
    "                if number % i == 0:\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        def jiecheng(number):\n",
    "            result = 1\n",
    "            for i in range(1, number+1):\n",
    "                result += i\n",
    "            return result\n",
    "\n",
    "        numprime = 0\n",
    "        for num in range(1,n+1):\n",
    "            if isprime(num):\n",
    "                numprime += 1\n",
    "        numnotprime = n - numprime\n",
    "        print(numprime,numnotprime)\n",
    "        result = jiecheng(numprime) * jiecheng(numnotprime)\n",
    "        return result % (10**9 + 7)\n",
    "        '''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        prime_num = self.countPrimes(n+1)\n",
    "        res1 = math.factorial(prime_num)%MOD\n",
    "        res2 = math.factorial(n-prime_num)%MOD\n",
    "        return res1*res2%MOD\n",
    "\n",
    "    \n",
    "    def countPrimes(self, n: int) -> int:\n",
    "        notPrime = [False] * n\n",
    "        res = 0\n",
    "        for i in range(2,n):\n",
    "            if notPrime[i] == False:\n",
    "                res += 1\n",
    "                j = i * i\n",
    "                while j < n:\n",
    "                    notPrime[j] = True\n",
    "                    j += i\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        numPrimes = sum(self.isPrime(i) for i in range(1, n + 1))\n",
    "        return self.factorial(numPrimes) * self.factorial(n - numPrimes) % (10 ** 9 + 7)\n",
    "\n",
    "    def isPrime(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        for i in range(2, int(sqrt(n)) + 1):\n",
    "            if n % i == 0:\n",
    "                return 0\n",
    "        return 1\n",
    "\n",
    "    def factorial(self, n: int) -> int:\n",
    "        res = 1\n",
    "        for i in range(1, n + 1):\n",
    "            res *= i\n",
    "            res %= (10 ** 9 + 7)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        numPrimes = sum(self.isPrime(i) for i in range(1, n + 1))\n",
    "        return self.factorial(numPrimes) * self.factorial(n - numPrimes) % (10 ** 9 + 7)\n",
    "\n",
    "    def isPrime(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        for i in range(2, int(sqrt(n)) + 1):\n",
    "            if n % i == 0:\n",
    "                return 0\n",
    "        return 1\n",
    "\n",
    "    def factorial(self, n: int) -> int:\n",
    "        res = 1\n",
    "        for i in range(1, n + 1):\n",
    "            res *= i\n",
    "            res %= (10 ** 9 + 7)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        numPrimes = sum(self.isPrime(i) for i in range(1,n+1))\n",
    "        return self.factorial(numPrimes) * self.factorial(n - numPrimes) % (10 ** 9 + 7)\n",
    "       \n",
    "\n",
    "    def isPrime(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        for i in range(2, int(sqrt(n)) + 1):\n",
    "            if n % i == 0:\n",
    "                return 0\n",
    "        return 1\n",
    "\n",
    "    def factorial(self, n: int) -> int:\n",
    "        res = 1\n",
    "        for i in range(1, n+ 1):\n",
    "            res *= i\n",
    "            res %= (10 ** 9 + 7)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        data_list = [2,3,5,7,11,13,17, 19,23,29,31,37,41,43,47,53,59, 61,67,71,73,79,83,89,97]\n",
    "\n",
    "        odd_number = 0\n",
    "        for cur_n in data_list:\n",
    "            if cur_n<=n:\n",
    "                odd_number += 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        result = 1\n",
    "        for cur_number in [odd_number, n -odd_number]:\n",
    "            while cur_number>1:\n",
    "                result *= cur_number\n",
    "                result%=(10**9+7)\n",
    "                cur_number -= 1\n",
    "        \n",
    "        return result\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def is_prime(self,n:int):\n",
    "        if n <= 1:\n",
    "            return False\n",
    "        elif n <= 3:\n",
    "            return True\n",
    "        elif n % 2 == 0 or n % 3 == 0:\n",
    "            return False\n",
    "        i = 5\n",
    "        while i * i <= n:\n",
    "            if n % i == 0 or n % (i + 2) == 0:\n",
    "                return False\n",
    "            i += 6\n",
    "        return True\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        res = 1\n",
    "        cnt = 0\n",
    "        for i in range(2,n+1):\n",
    "            if(self.is_prime(i)):\n",
    "                print(i)\n",
    "                cnt +=1\n",
    "                res *= cnt\n",
    "        hcnt = n-cnt\n",
    "        print(hcnt,cnt)\n",
    "        for j in range(1,hcnt+1):\n",
    "            #/print(j,res)\n",
    "            res = res*j\n",
    "        return res % (pow(10,9)+7)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        s = set([2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,\n",
    "                 61, 67, 71, 73, 79, 83, 89, 97])\n",
    "        num1 = 0\n",
    "        for i in range(1,n+1):\n",
    "            if i in s:\n",
    "                num1 += 1\n",
    "        num2 = n-num1\n",
    "        return (factorial(num1)*factorial(num2)) % (1000000007)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        isPrime = 0\n",
    "        for i in range(2,n+1):\n",
    "            if self.Prime(i):\n",
    "                isPrime += 1\n",
    "        notPrime = n-isPrime\n",
    "        out = 1\n",
    "        for i in range(2,isPrime+1):\n",
    "            out *= i\n",
    "        for i in range(2,notPrime+1):\n",
    "            out *= i\n",
    "        return out%(10**9+7) \n",
    "\n",
    "    def Prime(self,x):\n",
    "        for i in range(2,int(x**1/2)+1):\n",
    "            if x % i == 0:\n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        numPrimes = sum(self.isPrime(i) for i in range(1, n + 1))\n",
    "        return self.factorial(numPrimes) * self.factorial(n - numPrimes) % (10 ** 9 + 7)\n",
    "\n",
    "    def isPrime(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        for i in range(2, int(sqrt(n)) + 1):\n",
    "            if n % i == 0:\n",
    "                return 0\n",
    "        return 1\n",
    "\n",
    "    def factorial(self, n: int) -> int:\n",
    "        res = 1\n",
    "        for i in range(1, n + 1):\n",
    "            res *= i\n",
    "            res %= (10 ** 9 + 7)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        numPrimes = sum(self.isPrime(i) for i in range(1,n+1))\n",
    "        return self.factorial(numPrimes)*self.factorial(n-numPrimes)%(10**9+7)\n",
    "\n",
    "    def isPrime(self, n:int) -> int:\n",
    "        if n==1:\n",
    "            return 0\n",
    "        for i in range(2,int(sqrt(n))+1):\n",
    "            if n%i==0:\n",
    "                return 0\n",
    "        return 1\n",
    "\n",
    "    def factorial(self, n:int) -> int:\n",
    "        res =1\n",
    "        for i in range(1,n+1):\n",
    "            res *= i\n",
    "            res %= (10**9+7)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 埃氏筛\n",
    "MX = 10 ** 2 + 1\n",
    "primes = []\n",
    "is_prime = [True] * MX\n",
    "for i in range(2, MX):\n",
    "    if is_prime[i]:\n",
    "        primes.append(i)\n",
    "        for j in range(i * i, MX, i):\n",
    "            is_prime[j] = False\n",
    "primes.extend((MX, MX))  # 保证下面下标不会越界\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        def cal(n):\n",
    "            ans = 1\n",
    "            while n:\n",
    "                ans *= n \n",
    "                n -= 1\n",
    "            return ans\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(1, n + 1):\n",
    "            ans += is_prime[i]\n",
    "        \n",
    "        return cal(ans - 1) * cal(n - ans + 1) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]\n",
    "MOD = 10**9 + 7\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        assert 1<=n<=100\n",
    "        i = bisect_right(PRIMES, n)\n",
    "        return factorial(i) * factorial(n-i) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        def factorial(n):\n",
    "            if (n<=1):\n",
    "                return 1\n",
    "            return n*factorial(n-1)\n",
    "\n",
    "        def countPrimes(n):\n",
    "            sieve = [1] * (n + 1)\n",
    "            sieve[0], sieve[1] = 0, 0\n",
    "            for i in range(2, int(n**0.5) + 1):\n",
    "                if sieve[i]:\n",
    "                    sieve[i * i: n + 1: i] = [0] * len(range(i * i, n + 1, i))\n",
    "            return sum(sieve)\n",
    "\n",
    "        primeCount = countPrimes(n)\n",
    "        return factorial(primeCount)*factorial(n-primeCount)%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        def valid_prime(n: int):\n",
    "            if n == 1 or n == 0:\n",
    "                return False\n",
    "            for i in range(2, int(n ** 0.5) + 1):\n",
    "                if n % i == 0:\n",
    "                    return False\n",
    "            return True\n",
    "        def mul_n(n: int):\n",
    "            if n == 1 or n == 0:\n",
    "                return 1\n",
    "            return (mul_n(n-1) * n) % (10 ** 9 + 7)\n",
    "        count = 0\n",
    "        for i in range(1, n+1):\n",
    "            if valid_prime(i):\n",
    "                count += 1\n",
    "        return mul_n(count) * mul_n(n - count) % (10 ** 9 + 7)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        primes=[1]*(n+1)\n",
    "        primes[0],primes[1]=0,0\n",
    "        for i in range(2,int(sqrt(n)+1)):\n",
    "            if primes[i]==0:\n",
    "                continue\n",
    "            k=i*2\n",
    "            while k<=n:\n",
    "                primes[k]=0\n",
    "                k+=i\n",
    "        p=sum(primes)\n",
    "        np=n-p\n",
    "        if p>np:\n",
    "            p,np=np,p\n",
    "        t=pow(10,9)+7\n",
    "        r=1\n",
    "        for i in range(2,p+1):\n",
    "            r=r*i%t\n",
    "        r=r*r%t\n",
    "        for i in range(p+1,np+1):\n",
    "            r=r*i%t\n",
    "        return r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        numPrimes = sum(self.isPrime(i) for i in range(1, n + 1))\n",
    "        return self.factorial(numPrimes) * self.factorial(n - numPrimes) % (10 ** 9 + 7)\n",
    "\n",
    "    def isPrime(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 0\n",
    "        for i in range(2, int(sqrt(n)) + 1):\n",
    "            if n % i == 0:\n",
    "                return 0\n",
    "        return 1\n",
    "\n",
    "    # 求阶乘\n",
    "    def factorial(self, n: int) -> int:\n",
    "        res = 1\n",
    "        for i in range(1, n + 1):\n",
    "            res *= i\n",
    "            res %= (10 ** 9 + 7)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        def pre(n):\n",
    "            if n < 2:\n",
    "                return False\n",
    "            i = 2\n",
    "            while i * i <= n:\n",
    "                if not n % i:\n",
    "                    return False\n",
    "                i += 1\n",
    "            return True\n",
    "        \n",
    "        n1 = sum(1 for i in range(n+1) if pre(i))\n",
    "        n2 = n - n1\n",
    "        ans1,ans2 = 1,1\n",
    "        for i in range(1,n1+1):\n",
    "            ans1 *= i \n",
    "        for i in range(1,n2+1):\n",
    "            ans2 *= i\n",
    "        return (ans1 * ans2) % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        \n",
    "        cnt_p = 0 #质数的个数\n",
    "        sum_p = 1 #质数的个数全排列和\n",
    "        \n",
    "        cnt_n = 1 #非质数的个数\n",
    "        sum_n = 1 #非质数的个数全排列的和\n",
    "        \n",
    "        for i in range(2, n + 1): \n",
    "            if self.isPrime(i):\n",
    "                cnt_p += 1\n",
    "                sum_p *= cnt_p\n",
    "            else:\n",
    "                cnt_n += 1\n",
    "                sum_n *= cnt_n\n",
    "        \n",
    "        #质数个数的全排列 * 非质数个数的全排列\n",
    "        return (sum_p * sum_n) % (10**9 + 7)\n",
    "        \n",
    "    def isPrime(self, num: int) -> bool:\n",
    "        i = 2\n",
    "        while i * i <= num:\n",
    "            if num % i == 0:\n",
    "                return False\n",
    "            i += 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def isPrime(n):\n",
    "    p = 2\n",
    "    while p * p <= n:\n",
    "        if n % p == 0:\n",
    "            return False\n",
    "        p += 1\n",
    "    return True\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        np = sum(isPrime(i) for i in range(2, n+1))\n",
    "        ans = 1\n",
    "        for i in range(2, np+1):\n",
    "            ans = ans * i % 1000000007\n",
    "        for i in range(2, n-np+1):\n",
    "            ans = ans * i % 1000000007\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        def isprime(x):\n",
    "            if x==1:\n",
    "                return False\n",
    "            for i in range(2,x):\n",
    "                if x%i==0:\n",
    "                    return False\n",
    "            return True\n",
    "        a=sum(isprime(i) for i in range(1,n+1))\n",
    "        b=n-a\n",
    "        ans=1\n",
    "        for i in range(1,b+1):\n",
    "            ans*=i\n",
    "            ans%=1000000007\n",
    "        for j in range(1,a+1):\n",
    "            ans*=j\n",
    "            ans%=1000000007\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numPrimeArrangements(self, n: int) -> int:\n",
    "        # 如1~n中有x个质数, 那么数组中就有对应的x个质数索引可以摆放它们\n",
    "        # 非质数有y个(也就是n-x)\n",
    "        # 方案总数为 x*(x-1)*(x-2)*...*1 * y*(y-1)*...*1\n",
    "\n",
    "        # 埃式筛法, 计算出1~n中有几个质数\n",
    "        def countPrime(n):\n",
    "            if n <= 1:\n",
    "                return 0\n",
    "            st = [True] * (n+1)  # st[i]标记i是否为质数\n",
    "            count = 0\n",
    "            for i in range(2, n+1):\n",
    "                if st[i] is True:  # 如果i是质数\n",
    "                    count += 1\n",
    "                    for j in range(2*i,n+1,i):\n",
    "                        st[j] = False\n",
    "            return count\n",
    "        \n",
    "        x = countPrime(n)\n",
    "        y = n-x\n",
    "        ans = 1\n",
    "        for i in range(x, 0, -1):\n",
    "            ans*=i\n",
    "        for j in range(y, 0, -1):\n",
    "            ans*=j\n",
    "        return ans%(10**9+7)\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
